
/**
 * 
 * @param {array} x 
 * @param {array} y 
 * @description 暴力枚举法求解 x 和 y 的最长公共子序列
 */
function LCS_enumeration(x,y) {
    
    // 1.定义 l、s 两个指针分别指向两个序列，定义变量存放最长子序列及其长度，
    let l = null,
        s = null,
        longestSet = [];

    let lLen,
        sLen;
        

    // 2.判断 x，y 两个序列的长度
    if(x.length > y.length) {
        l = x;
        s = y;
        
    }else {
        l = y;
        s = x;
    }
    lLen = l.length;
    sLen = s.length;

    // 3.找出长度小的序列的所有子序列
    function getSubsets(nums) {

        // 迭代实现
        const len = nums.length;
        const subsLen = Math.pow(2,len);
            
        let subs = [];
    
        // 0 到 subslen-1 一共 subsLen 个子序列 
        for(let i = 0;i < subsLen;i++) {
            
            let sub = [];
            // 根据 i的二进制位形式得到一个子序列
            for(let j = 0;j < len;j++) {
    
                // 判断 i 的二进制形式的第 j+1 位是 0 还是 1，借助位运算
                if(i & (1<<j)) {
    
                    sub.push(nums[j]);
                }
            }
            
            subs.push(sub);
    
        }
    
        return subs;
        
    };

    var subsets = getSubsets(s);


    // 4.在长度更长的序列里查找是否有相同的子序列，并和最长子序列的长度比较，并更新最长子序列
    
    // 4.1 一个序列是否是另一个序列的子序列 双指针
    /**
     * 
     * @param {array} x 
     * @param {array} y 
     * @returns {boolean} 
     * @description 返回 true 代表 x 是 y 的子串，反之不是
     */
    function isSubset(x,y) {

        let i = 0,
            j = 0;
        let xLen = x.length,
            yLen = y.length;
        let flag = true;

        while(i < xLen && j < yLen) {

            if(x[i] === y[j]) {

                i++;
                j++;
            }else {
                j++;
            }
        }

        if(i === xLen && j <= yLen) {

            return true;
        }


        return false;
    }

    // 4.2 在 s 的子序列数组中找到 l 的最长子序列
    subsets.forEach(subset => {

        if(isSubset(subset,l) && subset.length > longestSet.length) {

            longestSet = subset;
            
        }
    })

    return longestSet;

    
}



/**
 * 
 * @param {array} x 
 * @param {array} y 
 * @description 动态规划实现 LCS
 */
function LCS(x,y) {

    const xLen = x.length,
        yLen = y.length;

    let L = [], // 记录长度
        B = []; // 记录是由哪个子问题得来的,
                // 0:由i,j-1得到
                // 1：由 i,j 得到
                // 2：由 i-1,j 得到
    
    // 初始化 L
    let temp = [];
    temp.length = yLen + 1;
    temp.fill(0);
    L.push(temp);
    for(let i = 0;i < xLen;i++) {
        L.push([0]);
    }

    // 初始化 B
    for(let i = 0;i < xLen;i++) {

        B.push([]);
    }


    // 得到子问题的解的记录 L, 和 标记数组(记录当前位置的解是由哪个子问题得到的)
    for(let i = 1;i < xLen + 1;i++) {

        for(let j = 1;j < yLen + 1;j++) {

            if(x[i-1] === y[j-1]) {
                L[i][j] = L[i-1][j-1] + 1;

                B[i-1][j-1] = 1;

            }else {
                if(L[i-1][j] > L[i][j-1]) {
                    L[i][j] = L[i-1][j];
                    B[i-1][j-1] = 0;

                }else {
                    L[i][j] = L[i][j-1];
                    B[i-1][j-1] = 2;

                }
            }

        }

    }


    // 根据标记数组得到 x 和 y 的最长公共子序列
    // 从后往前查 B,遇到第一个 1 停止，然后根据下标查 L
    function getLCSFromB(B,x,m,n) {
        
        if(m < 0 || n < 0) {

            return [];
        }

        if(B[m][n] === 1) {
            
            return [...getLCSFromB(B,x,m-1,n-1),x[m]];
        }else if(B[m][n] === 0) {

            return getLCSFromB(B,x,m-1,n);
        }else {
            return getLCSFromB(B,x,m,n-1);
        }

    }

    return getLCSFromB(B,x,xLen-1,yLen-1);
    

    
}






function testLCS(LCS_enumeration,LCS)  {

    function getRandomStr() {

        return Math.random().toString(10).slice(2);
    }
    let x = getRandomStr().split(''),
    y = (getRandomStr()+getRandomStr()).split('');


    console.log(`------------------\nx:${x}\ny:${y}`);

    console.log('暴力枚举法：',LCS_enumeration(x,y));

    console.log('动态规划法：',LCS(x,y));
}

for(let i = 0;i < 10;i++) {
    testLCS(LCS_enumeration,LCS);
}





